﻿namespace PugLib.Collections
{
	// Shawn Poulson, http://explodingcoder.com
	// 2010.02.04
	//
	// Released under Creative Commons Attribution-Share Alike license
	// http://creativecommons.org/licenses/by-sa/2.5/

	using System;
	using System.Collections.Generic;

	/// <summary>
	/// Caching algorithms.
	/// </summary>
	/// <remarks>
	/// Memoization algorithm derived from works:
	/// http://diditwith.net/2007/02/12/UsingAutomaticMemoization.aspx
	/// http://bartdesmet.net/blogs/bart/archive/2008/10/21/memoization-for-dummies.aspx
	/// 
	/// Variations of Memoize methods:
	/// Memoize(function)
	///  - Returns memoized delegate of function.
	/// Memoize(function, cache)
	///  - Returns memoized delegate of function, utilizing a user supplied
	///    IDictionary container.
	/// 
	/// Each method has a function signature for non-recursive and recursive
	/// function delegates.  The recursive signature allows for functions
	/// that must call its memoized self, to avoid unnecessarily rerunning
	/// function from within.
	/// 
	/// By itself, memoize is a static cache incapable of invalidating
	/// memoized values, ideal for deterministic functions.
	/// 
	/// Additional strategies can be used to accomodate invalidation:
	/// Provide Memoize with ValidationDictionary and a validation predicate.
	/// Set Memoize generic type to an implementation of IValidation for
	/// per-element validation.
	/// </remarks>
	public static class Memos
	{
		/// <summary>
		/// Memoize a single input function.
		/// </summary>
		/// <typeparam name="TArg">Input type</typeparam>
		/// <typeparam name="TResult">Output type</typeparam>
		/// <param name="function">Function delegate</param>
		/// <returns>Memoized function delegate</returns>
		public static Func<TArg, TResult> Memoize<TArg, TResult>(Func<TArg, TResult> function)
		{
			return Memoize(function, new Dictionary<TArg, TResult>());
		}

		/// <summary>
		/// Memoize a single input function.
		/// </summary>
		/// <typeparam name="TArg">Input type</typeparam>
		/// <typeparam name="TResult">Output type</typeparam>
		/// <param name="function">Function delegate</param>
		/// <param name="cache">User-supplied cache dictionary</param>
		/// <returns>Memoize function delegate</returns>
		public static Func<TArg, TResult> Memoize<TArg, TResult>(Func<TArg, TResult> function, IDictionary<TArg, TResult> cache)
		{
			return key => cache.ContainsKey(key) ? cache[key] : (cache[key] = function(key));
		}

		/// <summary>
		/// Memoize a single input recursive function.
		/// </summary>
		/// <remarks>
		/// The function delegate includes a delegate argument that can be used for memoized recursion.
		/// </remarks>
		/// <typeparam name="TArg">Input type</typeparam>
		/// <typeparam name="TResult">Output type</typeparam>
		/// <param name="function">Function delegate</param>
		/// <returns>Memoized function delegate</returns>
		public static Func<TArg, TResult> Memoize<TArg, TResult>(Func<TArg, Func<TArg, TResult>, TResult> function)
		{
			return Memoize(function, new Dictionary<TArg, TResult>());
		}

		/// <summary>
		/// Memoize a single input recursive function.
		/// </summary>
		/// <typeparam name="TArg">Input type</typeparam>
		/// <typeparam name="TResult">Output type</typeparam>
		/// <param name="function">Function delegate</param>
		/// <param name="cache">User-supplied cache dictionary</param>
		/// <returns>Memoize function delegate</returns>
		public static Func<TArg, TResult> Memoize<TArg, TResult>(Func<TArg, Func<TArg, TResult>, TResult> function, IDictionary<TArg, TResult> cache)
		{
			Func<TArg, TResult> memoizeFunction = null;
			return memoizeFunction = key => cache.ContainsKey(key) ? cache[key] : (cache[key] = function(key, memoizeFunction));
		}
	}
}